1. Field of the Invention
The present invention relates to the automated routing of circuit nets of integrated circuits, and more particularly to the automated routing of circuit nets for VLSI circuits having cell-based topologies.
2. Background of the Related Art
With the advent of circuit feature sizes in the sub-micron range, integrated circuits involving millions of transistors on a single chip have become commonplace. Due to the sheer number of devices on a single chip, an entire industry has evolved specifically to supply the semiconductor industry with software and hardware tools to automate much of the process of integrated circuit design.
There are two primary approaches to developing integrated circuits having Very Large Scale Integration (VLSI). One approach is the use of gate arrays. Gate arrays are integrated circuits having a fixed number of identical sites, each site comprising a number of simple circuit elements. The circuit elements are configured in a manner which enables easy implementation of common logic circuits such as transfer gates, inverters, nand gates, etc., depending upon how they are connected. A gate array can then be used to implement a specific circuit design simply by specifying the interconnection between the otherwise standard circuit elements. The particular interconnections of the circuit elements that are necessary to achieve a design are typically expressed as a netlist. The netlist defining the interconnections among the circuit elements of the gate array is often generated by other design synthesis tools.
A typical gate array floor plan called a base, is shown in FIG. 1A. The topology of a gate array base is predefined by the gate array manufacturer. The circuit elements are arranged in rows 10 with a predetermined distance 12 between the rows as shown. Another gate array topology configures the circuit elements 20 in an array format as shown in FIG. 1C, also known as a "sea of gates."
A second approach to the design of VLSI integrated circuits is the use of standard cells. Like gate arrays, standard cell designs rely on a set of predefined circuit elements called cells with which to implement the design. Unlike gate arrays, however, the complexity of standard cells can range from simple logic gates such as those found in gate arrays to block-level components such as RAMs, ROMs, and PLAs. The standard cells are typically stored in a standard cell library, and are retrieved from the library as specified by the netlist of the design. The block-level components can be built from the lower level cells of the library and can also be stored in the library for duplication as required by a netlist. Further, standard cell designs are not topologically fixed. Rather, standard cells can be placed anywhere on the integrated circuit being designed. A typical standard cell (i.e. cell-based) floor plan is shown in FIG. 1B.
The primary advantage of gate array designs is that the manufacturer can mass produce a large quantity of identical circuit bases which are typically completed up to the stage of the process where interconnections are made. A circuit designer can then provide a netlist to the manufacturer which defines all of the interconnections among the available circuit elements on a particular base. The manufacturer can use the netlist to create the masks necessary to produce the interconnections for the completed circuit, and complete the manufacturing process accordingly. Thus, non-recoverable engineering (NRE) costs are relatively low and design turnaround time relatively short.
One of the downsides of the fixed topology of a gate array is that for a given design there are a limited number of circuit elements that can be interconnected to produce the design. Thus, if a VLSI circuit design as specified by a particular netlist requires more circuit elements than are provided on a particular gate array, or if there is insufficient room available to complete the interconnections among the available circuit elements, one must move to the next larger gate array base in order to implement the design, even if this means wasting silicon area.
The primary advantage of cell-based designs is that greater circuit densities can be achieved. This is because the size of the circuit is typically determined during the routing process and need only be large enough to accommodate the final placement and interconnection of the cells. Another advantage is greater functionality due to the hierarchial nature of cell-based designs.
The cell-based topology shown in FIG. 1B has random logic, typically comprised of low level cells, arranged as rows 14 much like the rows of gate array circuit elements in FIG. 1A. The topology also includes complex functional blocks 16, which can be designed from scratch or can be conglomerations of lower-level cells. The complex functional blocks are represented in the netlist in the same manner as the lower-level cells. That is, they are specified as a function of their interconnections among the other blocks and cells. Channels 18 are initially defined for purposes of routing interconnections among the rows of cells 14 and the high-level functional blocks 16. A pure hierarchial approach might further integrate random logic rows 14 into one or more higher-level blocks.
A number of algorithms have been developed and implemented to facilitate the automatic routing of interconnections among the circuit elements of both gate array and cell-based circuit designs. Such algorithms are integrated into software tools called routers, which take as part of their input a netlist description of the desired circuit design. These tools attempt to automatically route the interconnections among the circuit elements of the gate array, or the standard cells and functional blocks of cell-based designs, as specified by the netlist.
Routing algorithms as incorporated into tools for routing gate arrays are considerably different from those algorithms employed in tools for routing cell-based designs. This is due primarily to the fact that gate array topologies are fixed while cell-based topologies are not. Further, cell-based designs have been heretofore based primarily on the routing of channels between rows and blocks, while "sea of gates" gate array topologies have no predefined channels between circuit elements. Finally, because cell-based designs are typically hierarchial in nature, the routing of cell-based designs are also typically hierarchial in nature. Interconnections within complex functional blocks of cell-based designs can be routed first and optimized such that the final routing of the cell-based design involves only routing connections among the various functional blocks.
Often, tools for routing interconnections among the cell-based designs employ routers which are designed for a particular type of functional block. For example, certain routers are designed specifically to handle common structures such as RAMs and ROMs. Once these high level blocks are routed and optimized using these specialized routers, the routing of the interconnections among the functional blocks of the cell-based design becomes less complex.
As applied to gate arrays, channel routers are not permitted to adjust (d) 20 between the rows, although they can add pass-through connections 27 to permit interconnections to pass through the rows as illustrated by interconnect line 25 of FIG. 2A.
Most routing tools currently available for automatically routing cell-based designs are based on "channel" router algorithms. Versions of channel router algorithms are also used for gate array topologies that are row-based. The channel router evolved at a time when both gate arrays and cell-based designs were arranged in rows as shown in FIG. 2A. The classical channel router attempts to route the interconnections in the channels 26 between the rows of cells 22. Because the location of the circuit elements comprising the standard cells of a cell-based design are not already fixed, the channel router has the freedom to adjust the distance (d) 20 between the rows of cells 22 as well as the width (w) 24 of the cells to accommodate the routing of the interconnections as specified by the netlist for the design. Thus, the circuit as finally routed might look something like that which is shown in FIG. 2B. The width of the cells (W) 26 have been increased to accommodate pass through connections 30 and the distance between rows (D) 28 have been expanded to accommodate the number of interconnections that must run between the rows of cells 22. FIGS. 3A and 3B illustrate the expansion of channels by a channel router as applied to a block-level cell-based design.
FIG. 4 shows an exploded view of a row-based topology. Each circuit cell 44 has input and/or output connectors 40 by which the cells 44 are interconnected with one another. The netlist defines the various circuit nets as connections between input and output connectors of components or cells comprising the circuit. As applied to cell-based designs, the channel router is designed to minimize the width (w) of the channel 48 while accommodating all of the interconnections between the rows of cells 42 which define the channel 48. As applied to row-oriented gate arrays, the channel router attempts to route all of the nets using the predefined width of the channel 48.
A number of assumptions were made in the development of channel router algorithms. Among these assumptions are that the channel 48 is always rectangular in nature, that there are no obstructions to routing interconnections through the channel 48, all of the connectors 40 emanating from the various cells 44 are contained within the boundaries of the channel 48. Additionally, any of the connections which extend beyond the length of the channel (e.g. connection 46) are floating and can be located anywhere within the width of the channel. Stated differently, there is no predefined order with respect to the position of a particular connection within the channel. Still further, most channel routers were designed for use with two levels of interconnect. One was typically assigned to vertically extending portions 41 of the connections 46 and the other to the horizontally extending portions 43 of the connections 46 running parallel with the channel. Of course, the channel router will also be constrained by the ground rules of the particular process being used to fabricate the integrated circuit, including the minimum width of the connections 46, as well as the minimum distance between the various connections 46.
Over the years, many extensions of the classic channel router have been made, including the permissibility of specifying connectors 40 inside cells 44 as opposed to only at their border with the channel, the ability to have cells 44 which do not necessarily have the same widths or heights, as well as more than two layers of interconnect. Unfortunately, none of these "improvements" were able to improve the performance of the channel router much beyond the classic case as shown in FIG. 4.
Another well-known routing algorithm is known as a maze router. The algorithm employed is also known as wave propagation. The maze router overlays a grid 56 on the topology of cells or circuit elements, with each intersection of the grid 58 representing either connectors or spaces through which interconnect can be run. The maze router identifies a source connector 50 and a target connector 52 to which the source connector must be connected, in accordance with the netlist of the circuit design. The maze router then explores every possible route available to connect the source connector 50 to the target connector 52. Certain of the interconnect routes will already be blocked either by the presence of other connectors or circuit elements. This is represented by locations 54. The maze router assigns a cost to each neighboring point, the cost being associated with the physical realities of committing a particular net to run through that point. Although this particular algorithm will always find a path from source to target if one exists, because it evaluates every possible avenue of connection, it is extremely slow and extremely memory intensive. Of course, numerous attempts have been made to optimize the maze router for speed and memory capacity. Despite these attempts, however, the maze router continues to be cumbersome.
Probe routers, like maze routers, attempt to find a path from source to target. FIG. 6 illustrates an example of a line probe router determining a path between a source 60 and a target 66. The line probe router starts at the source and attempts to generate two lines, one in the X direction one in the Y direction. It then attempts to determine the longest line that it can run while still moving towards the target before it hits an obstruction 62. At the end of the line 64 the probe router then expands two more lines in the X and Y directions and again determines the longest line it can run while still moving in the general direction of the target 66. Eventually the line probe router finds the series of vertical and horizontal lines which will connect the source to the target. The line probe router is much faster than the maze router. Unlike the maze router, the line probe router does not promise to find a solution even if one does exist, nor does it promise to find the cheapest solution. There have also been attempts to produce hybrids of maze and line probe routers, to exploit the best features of both routers.
Maze and line probe routers are typically applied to special cases where only one layer of metal is available for interconnecting devices. Such routers are not readily applicable to general purpose situations.
Another type of routing algorithm is illustrated in FIG. 9 which is also grid oriented. Called bin-based routing, each line 98 on the two-dimensional grid 90 is called a bin boundary and each rectangular area 92 is called a bin. Each bin boundary has a certain capacity for interconnect lines crossing it. The capacity of each bin boundary 98 is determined by constraints imposed by the fixed gate array topology. Circuit structures 96 can limit a bin boundary's capacity, as well as the design rules for the process. The grid can be made coarse or fine, depending upon the level of detail at which the router is operating. This type of routing is most applied to "sea of gates" gate array topologies.
Most currently available design tools are hierarchial in nature, and often employ more than one type of routing algorithm. Most routing tools used for cell-based designs begin with the placement of circuit elements, cells and/or cell blocks. Placement can be manual or automated, and typically attempts to make intelligent decisions about where connectors to the circuit elements, cells and/or cell blocks should be located as well as how cells and/or blocks should be oriented and positioned relative to one another. Such decisions can be driven by considerations of circuit compaction, number of interconnect lines running between the blocks, etc. Of course, with gate arrays there is no placement step because this process has already been forced on the designer by the manufacturer.
The next step is typically a global routing step, which is an attempt to logically determine what general paths each interconnection is going to take to accomplish its designated connections. These decisions are made based on the available avenues formed by the current placement of circuit elements and/or blocks, and are assigned in consideration of various costs (i.e. such as to incur the shortest amount of interconnect between the connectors).
Gate array global routers employing bin-based routing will attempt to assign to each bin boundary those connectors which are to cross a given bin boundary, although typically not the order in which they cross. As previously mentioned, most cell-based routing tools employ channel-based routing so their global routers are typically assigning various interconnect lines to the available channels. Again, the cell-based global routers do not assign the ordering of the interconnect lines running through the channels.
Once the global router has assigned the general flow of interconnect lines, a detailed router takes over and actually attempts to make the interconnect lines fit the assignments made by the global router. In the case of the gate array design, the detailed router knows it can make the routing because the global router was assigning lines to bin boundaries based on fixed capacities. Because most routing tools applied to cell-based designs employ channel routers as their detailed routers, however, the circuit elements or blocks along the channels are subject to being moved by the channel router.
As previously mentioned, most cell-based circuit designs are block-level or hierarchial in nature. A block-level standard cell design topology is illustrated in FIG. 7a. In most block-level designs, however, some of the blocks (e.g. block 79) are actually made up of classical standard cell random logic which is typically oriented into rows of cells. Present solutions to routing such circuit designs are typically packages made up of several different routers which are then applied in a hierarchial manner using the foregoing flow.
At the lowest levels, specialized routers are used to route specific types of cell blocks. Thus, routers which are optimally tailored for routing particular types of structures are used on memory blocks, ALU's and other high-level functional blocks. Channel routers are typically applied to route classic standard cell-based random logic. Once each of the higher level blocks has been routed, a new netlist is generated which simply represents the interconnections among the higher level blocks. Information detailing the physical locations of the connectors for the various blocks is also compiled. This information can then be used either manually or perhaps with some automated placement algorithm to arrange the blocks in accordance with criteria such as the number of lines running between certain of the blocks, the proximity and orientation of connectors of particular blocks, as well as the geometries of the blocks to minimize die area.
The use of channel routers as detailed routers on cell-based designs such as that shown in FIG. 7a imposes undesirable limitations on the circuit topology because of its ability to move circuit elements, cells and/or cell blocks right up until a given channel is completely routed. Using channel routers as detailed routers requires that the cells and/or blocks be arranged in a sliceable design configuration.
FIG. 7a shows slicing line 78 drawn through the arrangement of cell blocks for a proposed cell based circuit design. A sliceable design requires that slice line 78 be able to completely split the channels between the various cell blocks 72, 77 and 79. Each of the slice lines is given a unique slice line number with those slice lines splitting channels co-extensive with multiple blocks being assigned the lowest numbers and those slice lines which split channels co-extensive with single blocks given the highest numbers. The detailed router will then route each channel split by a slice line beginning with the slice line having the highest assigned number and proceeding in order down to the channel split by the slice line having the lowest assigned number.
The use of channel routers requires that this ordering be imposed on the channel router because the channel router is permitted to adjust the size of a channel based on the number of lines which must be run through that channel. Thus when the channel split by slice line 5 is routed, blocks 71 and 73 may be shifted by the channel router relative to one another as the channel router attempts to route all of the interconnect lines assigned to the channel by the global router through that channel. Until that channel has been completely routed, the positions of block 73 and 71 relative to one another are subject to change at any time. Thus the physical positions of the connectors of blocks 73 and 71, which are associated with the edges of those blocks co-extensive with the channel split by slice line 2 will not be fixed until the channel split by slice line 5 has been completely routed.
Furthermore, floating nodes 74, which are the positions of interconnect lines 70 as they emerge from the channels split by slice lines 4 and 3 and intersect with other channels, will not be fixed until the channels split by slice lines 4 and 3 have been completely routed. From the point of view of the channels split by slice line 2, these floating nodes look just like connectors emerging from edges of blocks co-extensive with that channel. Thus, it would be futile for the channel router to route the channels split by slice line 2 before the channels split by slice lines 4 and 5 have been routed. Of course, there is some flexibility with respect to this ordering as the channel split by slice line 4 could be routed before the channel split by slice line 5.
Boundary channels 76 will be the last boundaries to be routed by the channel router because all of the cell blocks will have been fixed in position relative to the boundaries of the chip and thus only the boundaries need be expanded to accommodate the interconnections that are to be routed through those boundary channels. Because the cell-based design must be sliceable, routing tools based on channel routers as detailed routers cannot route the non-sliceable design of FIG. 7B, even though it may be more compact that way.
As previously discussed, prior to applying the detailed router (i.e. channel router) to the various channels in accordance with the routing order as determined by the slicing of the topology, a global router is used to determine which of the interconnections as represented by the netlist of the circuit design should be routed through which of the channels between the cell blocks. Thus, it is the global router's job to optimize the assignment of the various interconnections described by the netlist to the various channels defined by the topology. In the example shown in FIG. 7a, the global router determined that interconnect line 70 would travel through the channel split by slicing line 4, then through the channel split by slicing line 2, and finally through the channel split by slicing line 3 to its connection to block 72. It also determined that the continuing connection would continue through the channel split by slicing line 2 and then through the vertical boundary channel coextensive with the right vertical edge of the block 72.
Once the global assignments have been made it becomes the job of the channel router to figure out how to route all of the lines through each channel as assigned by the global router. The channel router will typically estimate the space required by the channel for the number of lines that have been assigned to that channel by the global router. It then tries to figure out how to accomplish the routing using the estimated width of the channel. If it is unsuccessful in routing the channel using the estimated width, it simply expands the width by moving the location of the cell blocks relative to one another to increase the width of the channel. The channel router continues with this process until it is able to complete the routing of the channel. As previously mentioned, the global router does not determine the position of each line within the channel to which it has assigned the line. The placement of each line within the channel is completely left up to the channel router.
There are a number of limitations and disadvantages to cell-based routing tools employing channel routers as detailed routers in addition to the restrictions to sliceable topologies as just described. Nonrectangular shaped blocks are typically not permitted because channel routers are not designed to route channels formed by nonrectangular shapes, and because such geometries typically render the design nonsliceable. Further, the use of channel routers as a detailed router means that cell-block locations will be altered after the global routing process has been completed. Thus, decisions made by the global router as to which interconnect lines should optimally run through which of the channels, made based on then current cell block positions, cell and/or block connector locations, etc. can be rendered obsolete and therefore nonoptimal by the channel router as it moves the blocks to complete the routing of each channel.
FIG. 8 illustrates an example of when a decision made by a global router has been rendered obsolete by the channel router. Prior to the detailed routing step, the global router recognizes that connection 86 is most optimally routed through channel 80 between blocks 84 and 80. The next stage of FIG. 8, after detailed routing has occurred, illustrates what can happen to that formally optimal channel assignment if the channel router has shifted the blocks 84 and 82 during the process of routing all of the channels. Connection 86 is still made through channel 80 between blocks 84 and 82, but because the blocks have been shifted to the left by the channel routing process, what was formally an optimal channel assignment has become nonoptimal. This problem can become even more acute for large buses of 64 or even 128 lines. Even a very slight shift creates a huge problem when it comes to such large buses.
This type of problem can also occur when the routing tool is routing individual functional blocks or random logic blocks. Decisions about where it is best to locate connectors within the cell or block, pass-through lanes in the blocks for external lines, etc. can be rendered obsolete as the blocks themselves come out looking differently than originally planned.
Another disadvantage to the foregoing cell-based routing methodology is that channel based routers typically are not designed to handle the routing of circuits being fabricated in a process which has more than two levels of interconnect available. If some of the cell blocks of FIG. 7a have been internally routed with only two levels of interconnect, and the process used to fabricate the circuit has three or more levels available to it, levels of interconnect not used internally in those blocks could be run directly over the top of those blocks. Because of the way global routers and detailed routers are set up when the detailed router is a channel router, it is awkward to fool those routers into incorporating areas of those blocks into channels. Further, the decisions as to which portions of which blocks to assign to which channels must be made prior to the actual channel routing process. Again, because the channel router is able to move the locations of cell blocks as it completes its task of routing each channel, those decisions as to the allocation of routable block area to various channels can be obsoleted in the same way that decisions made by the global router as to which channels through which to run interconnect lines can become obsoleted by the channel routing process.
A still further constraint imposed on the efficient and optimal routing of cell-based designs by channel-based routing tools is the inability to handle prerouting of certain interconnect lines ahead of time, or to impose constraints on relative positionings of blocks, or on minimum or maximum allowable distances between blocks, interconnections or connectors.
Therefore, there is significant room for improvement in the art of automatically routing interconnections among cell-based circuit design topologies.
Because the topologies of gate arrays are fixed for the most part, even those which use modified versions of channel routers don't suffer from the problems discussed above with respect to cell-based routing tools. Global routers of gate array routing tools have fixed resources with which to work and either they can or can't accomplish the routing of all of the nets of the netlist given those resources. Of course routers for gate arrays are also less complex because they are free of the complexities engendered by having the freedom of moving (i.e. expanding or contracting) the resources.
The global router typically used to route a gate array topology such as the one shown in FIG. 2A basically makes the decision at what point 27 the interconnect lines must cross rows in order that connector 21 be interconnected with connector 23. Sometimes the global router will also drive a specialized algorithm which has the ability to add pass-through cells to the cells of the rows in order to accommodate or to create additional cross over points 27 by which interconnect lines are permitted to cross cells in the rows 22.
To route the gate array topology of FIG. 1C (i.e. "sea of gates"), a coarse grid 90 is typically superimposed by the global router over the top of the topology as shown in FIG. 9. The positioning of the grid 90 over the "sea of gates" topology by the global router can be, but is not necessarily, aligned with the rows and columns of circuit elements or cells. Thus the grid will have within each grid cell 92 various connectors 94 and various circuit elements or cells 96. The global router determines upfront which grid cell boundaries 98 will be crossed by which interconnect lines. Of course, the global router makes this decision in an attempt to route all of the nets or interconnections specified by the netlist of the circuit design while remaining within the given capacity of each of the bin boundaries.
Those of skill in the art have recognized the disadvantages of channel-based routing of cell-based designs, and that adapting gate array type routing schemes for use in the cell-based context is desirable. Cadence Design Systems has introduced a product called CELL 3, which has manual user interface. Permits a user to manually move cell and block placement around and try to route. If the router cannot, manually move the placement and try again. This is highly undesirable because it is not truly automated, nor is it likely to be optimal.